<html>
<head><meta charset="utf-8"><title>Flow-sensitive MIR const-propagation · t-compiler/wg-mir-opt · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/index.html">t-compiler/wg-mir-opt</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html">Flow-sensitive MIR const-propagation</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="208461037"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/208461037" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#208461037">(Aug 30 2020 at 00:27)</a>:</h4>
<p>I've opened <a href="https://github.com/rust-lang/rust/issues/76044">#76044</a> with the extension to the dataflow framework required to implement flow-sensitive const propagation. I don't know the current state of MIR const propagation, and I suspect there's more work to be done before switching to the dataflow-based approach. However, there should soon be one less blocker for those who wish to take this on.</p>



<a name="208486718"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/208486718" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Vandel Sillesen <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#208486718">(Aug 30 2020 at 14:07)</a>:</h4>
<p>So with <a href="https://github.com/rust-lang/rust/issues/76044">#76044</a> it should be possible remove bounds checks such as those presented in e.g. <a href="https://github.com/rust-lang/rust/issues/75525">#75525</a> by having a lattice that stores something like struct Bounds {lower: u128, higher: u128} where the bounds would get updated in transfer functions for e.g. Lt statements?</p>



<a name="208496437"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/208496437" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#208496437">(Aug 30 2020 at 17:49)</a>:</h4>
<p>That should be possible. You need to be careful about convergence for a lattice as big as the set of ranges of a 128-bit integer though. For instance, trying to model arithmetic operations in that context is a no-go, since incrementing a  counter in a loop would cause your analysis to hang indefinitely.</p>



<a name="208606119"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/208606119" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Vandel Sillesen <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#208606119">(Aug 31 2020 at 19:42)</a>:</h4>
<p>Sure. As a first draft an iteration limit should allow termination rather simply. I don’t know if you thoughts on anything more advanced?</p>



<a name="208607145"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/208607145" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#208607145">(Aug 31 2020 at 19:52)</a>:</h4>
<p>My thought was that your optimization will work better if arithmetic operations on a place cause that place to be assigned a maximally conservative range. This may have been your plan all along, but it wouldn't have been obvious to me. Hitting an iteration limit means that you cannot optimize <em>anything</em> in the function, since fixpoint wasn't reached.</p>



<a name="208608045"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/208608045" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#208608045">(Aug 31 2020 at 20:00)</a>:</h4>
<p>Modulo by a constant would be fine of course, but trying to model addition or subtraction by a constant is probably not a good idea.</p>



<a name="208654443"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/208654443" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jannis Harder <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#208654443">(Sep 01 2020 at 07:46)</a>:</h4>
<p>Is this something where widening (as in abstract interpretation) can be used? I don't have any practical experience with that, but from what I've read and understand they are used to avoid infinite or impractically long chains during fixpoint computations.</p>



<a name="208720724"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/208720724" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#208720724">(Sep 01 2020 at 17:30)</a>:</h4>
<p>Perhaps? I'm not familiar with that particular piece of jargon.  If it means: "Make a more conservative assumption about the possible values of a variable to speed up convergence", then yes.</p>



<a name="208724767"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/208724767" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jannis Harder <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#208724767">(Sep 01 2020 at 18:04)</a>:</h4>
<p>Yes, but instead of saying arithmetic operations are always approximated maximally conservative you do it dynamically instead, e.g. every time an interval grows, you require it to double in size, and if it doesn't you make it larger so it does</p>



<a name="208725061"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/208725061" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jannis Harder <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#208725061">(Sep 01 2020 at 18:06)</a>:</h4>
<p>At least that's my intuitive understanding, as I haven't used it myself I'm not sure how well that matches the actual theory... besides widening there is also something called narrowing, which you do after you find a fixed point to regain some of the precision lost during widening... but I don't have any intuition for that at all</p>



<a name="208726694"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/208726694" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jannis Harder <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#208726694">(Sep 01 2020 at 18:18)</a>:</h4>
<p>I sadly didn't keep notes when I last read about abstract interpretation and I wasn't really interested in widening/narrowing at that time, but I did remember that quickly finding the exact bounds for loops that increment counters was one of the prototypical examples, so I thought mentioning that here can't hurt</p>



<a name="208736764"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/208736764" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#208736764">(Sep 01 2020 at 19:35)</a>:</h4>
<p>Ah, that doubling strategy is an interesting compromise and certainly worth looking into.</p>



<a name="208743731"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/208743731" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Vandel Sillesen <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#208743731">(Sep 01 2020 at 20:28)</a>:</h4>
<p>Skimming chapter 7 of <a href="https://cs.au.dk/~amoeller/spa/">https://cs.au.dk/~amoeller/spa/</a> they describe another trick in widening. We can divide the u128 domain into intervals which can be seeded from the mir body. So for instance the intervals could be 0, 5, 8, Inf given that 5 and 8 are constants derived from e.g Lt and Gt statements. That should converge the algorithm faster</p>



<a name="208928692"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/208928692" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#208928692">(Sep 03 2020 at 07:17)</a>:</h4>
<p>to find out more about this, it is called "(value) range analysis" in the literature. But I guess this can also ask the question of representation: either we can use published algorithms to have their safety/soundness/efficiency properties but they mostly use SSA or e-SSA, or we have to adapt them and risk losing some of those properties (which is similar to Cranelift's situation in the past, prompting them to switch from EBBs to BBs)</p>



<a name="209132277"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/209132277" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#209132277">(Sep 04 2020 at 19:26)</a>:</h4>
<p>Hey <span class="user-mention" data-user-id="139182">@Simon Vandel Sillesen</span> today's the day my auto-imposed deadline of two weeks is due. Uni still hasn't got back to me <span aria-label="cry" class="emoji emoji-1f622" role="img" title="cry">:cry:</span> so that means I'm now definitely relinquishing the flow sensitive const-prop to you. Best of luck <span aria-label="sparkling heart" class="emoji emoji-1f496" role="img" title="sparkling heart">:sparkling_heart:</span></p>



<a name="209132325"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/209132325" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#209132325">(Sep 04 2020 at 19:27)</a>:</h4>
<p>Also, if I may suggest a cool name: you can totally call this feature "Non-Lexical Const Prop" ;)</p>



<a name="209151747"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive%20MIR%20const-propagation/near/209151747" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Vandel Sillesen <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation.html#209151747">(Sep 05 2020 at 00:09)</a>:</h4>
<p>Hey <span class="user-mention" data-user-id="212698">@Félix Fischer</span> sorry to hear about uni<span aria-label="exhausted" class="emoji emoji-1f625" role="img" title="exhausted">:exhausted:</span> I don't want to claim too much work, so feel free to start on it <span aria-label="smile" class="emoji emoji-1f642" role="img" title="smile">:smile:</span> I can only work some time of my free time in it anyway</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>